package com.lry.pda.bottom.c.frontend;


import java.util.Iterator;
import java.util.List;
import java.util.Map;


public class FirstSetBuilder {
	
    private Map<Integer, Symbols> symbolMap;
    private boolean runFirstSetPass = true;


    public FirstSetBuilder() {
    	this.symbolMap = Grammar.getSelf().getSymbolMap();
    }

    public boolean isSymbolNullable(int sym) {
    	Symbols symbol= symbolMap.get(sym);
    	if (symbol == null) {
    		return false;
    	}

    	return symbol.isNullable ? true : false;
    }


    public void runFirstSets() {
    	while (runFirstSetPass) {
    		runFirstSetPass = false;

    		Iterator<Symbols> it = symbolMap.values().iterator();
    		while (it.hasNext()) {
    			Symbols symbol = it.next();
    			addSymbolFirstSet(symbol);
    		}
    	}
    	printAllFirstSet();
		System.out.println("============");
    }

    private void addSymbolFirstSet(Symbols symbol) {
    	if (isSymbolTerminals(symbol.value) == true) {
    		if (symbol.firstSet.contains(symbol.value) == false) {
    			symbol.firstSet.add(symbol.value);
    		}
    		return;
    	}

		//遍历某个表达式的所有产生式，执行如下规则：
		//如果推导式右边第一个是终结符，那么firstSet把这个终结符加进来
		//规则1： s -> A a ，A是终结符，则A属于first（s）
		//规则2：s -> b a, s和b是非终结符，且b是非nullable的，则fist(s) = first(b)
		//规则3：s -> a1 a2 ...an b, a1~an是nullable的(nullable的肯定是非终结符)，b是非nullable的非终结符或者是一个终结符
		//那么first(s) = fisrt(a1) + first(a2) +...+first(an) + first(b);

    	for (List<Integer> rights:symbol.productions) {

    		if (null==rights||rights.isEmpty()) {
    			continue;
    		}

    		Integer firstSymbol = rights.get(0);

    		if (isSymbolTerminals(firstSymbol)) {
    			if(!symbol.firstSet.contains(firstSymbol)){
					runFirstSetPass = true;
					symbol.firstSet.add(firstSymbol);
				}
    		}
    		else{
    			int pos = 0;
    			Symbols curSymbol = null;
    			do {
    				curSymbol = symbolMap.get(rights.get(pos));
    				if (!symbol.firstSet.containsAll(curSymbol.firstSet)) {
    					runFirstSetPass = true;

    					for (int j = 0; j < curSymbol.firstSet.size(); j++) {
    						if (!symbol.firstSet.contains(curSymbol.firstSet.get(j))) {
    							symbol.firstSet.add(curSymbol.firstSet.get(j));
    						}
    					}
    				}
    				pos++;
    			}while(pos < rights.size() && curSymbol.isNullable);
    		}
    	}
    }

    private boolean isSymbolTerminals(int symbol) {
    	return CTokenType.isTerminal(symbol);
    }

    public void printAllFirstSet() {
    	Iterator<Symbols> it = symbolMap.values().iterator();
		while (it.hasNext()) {
		    Symbols sym = it.next();
		    printFirstSet(sym);
		}
    }

    private void printFirstSet(Symbols symbol) {

    	String s = CTokenType.getSymbolStr(symbol.value);
    	s += "{ ";
    	for (int i = 0; i < symbol.firstSet.size(); i++) {
    		s += CTokenType.getSymbolStr(symbol.firstSet.get(i)) + " ";
    	}
    	s += " }";

    	System.out.println(s);
    	System.out.println("============");
    }

    public List<Integer> getFirstSet(int symbol) {
    	Iterator<Symbols> it = symbolMap.values().iterator();
		while (it.hasNext()) {
		    Symbols sym = it.next();
		    if (sym.value == symbol) {
		    	return sym.firstSet;
		    }
		}
		return null;
	
    }
    
 
}
